1. Field of the Invention
The present invention relates to a Huffman decoding method and decoder, a Huffman decoding table, a method of preparing the table, and storage media storing respective programs for executing the methods.
2. Description of the Related Art
Huffman coding encodes symbols by assigning thereto respective codewords having lengths corresponding to probabilities of occurrence of the symbols to thereby minimize the average length of encoded symbols. Huffman coding is known as a typical method of entropy encoding (variable length encoding), and widely used e.g. in compression of multi-media data, such as image data and voice data.
An example of a conventional Huffman decoder will be described with reference to FIGS. 6 to 8. It is assumed here that input data encoded by using a Huffman coding table shown in FIG. 6 are decoded. That is, data (symbol) xe2x80x9cAxe2x80x9d is assigned with a codeword xe2x80x9c1xe2x80x9dhaving a code length of 1 (bit), data xe2x80x9cBxe2x80x9d a codeword xe2x80x9c00xe2x80x9d having a code length of 2(bits), data xe2x80x9cCxe2x80x9d a codeword xe2x80x9c010xe2x80x9d having a code length of 3(bits), data xe2x80x9cDxe2x80x9d and xe2x80x9cExe2x80x9dcodewords xe2x80x9c01111xe2x80x9d and xe2x80x9c01100xe2x80x9d each having a code length of 5 (bits), data xe2x80x9cFxe2x80x9d a codeword xe2x80x9c011101xe2x80x9d, having a code length of 6 (bits), and data xe2x80x9cGxe2x80x9d, xe2x80x9cHxe2x80x9d, xe2x80x9cIxe2x80x9d, xe2x80x9cJxe2x80x9d, xe2x80x9cKxe2x80x9d, and xe2x80x9cLxe2x80x9d codewords xe2x80x9c0111001xe2x80x9d, xe2x80x9c0111000xe2x80x9d, xe2x80x9c0110111xe2x80x9d, xe2x80x9c0110110xe2x80x9d, xe2x80x9c01101010xe2x80x9d, and xe2x80x9c0110100xe2x80x9d each having a code length of 7, respectively.
FIG. 7 shows the construction of the conventional Huffman decoder.
In the figure, reference numeral 31 designates a codeword table storing codewords of the Huffman coding table shown in FIG. 6, reference numeral 32 designates a code length table storing code lengths associated with the respective codewords, and reference numeral 33 designates a data table storing decoded data associated with the respective codewords. Further, reference numerals 34, 35, 36 designate a counter for supplying a read address to the codeword table 31, the code length table 32, and the data table 33, an input data-acquiring circuit for acquiring input data D having the number of bits determined based on a code length (represented by xe2x80x9clengthxe2x80x9d in the figure) read out from the code length table 32, from a stream of input data encoded by Huffman coding, and an agreement-detecting circuit for detecting agreement between a codeword read from the codeword table 31 and the input data D supplied from the input data-acquiring circuit 35.
The flow of processing by the conventional Huffman decoder constructed as described above will be described with reference to. FIG. 8.
First, in a step S21, the input data D retrieved by the input data-acquiring circuit 35, the count n of the counter 34 (i.e. read address for the tables 31 to 33) and code length data L are all set to an initial value 0. Then, the process proceeds to a step S22, wherein an address #n (n=0 immediately after the initialization) of the code length table 32 is accessed to read out a code length therefrom.
Then, the process proceeds to a step S23, wherein it is determined whether or not the code length read out agrees with the code length data L. In the case of n=0, the code length read out from the code length table 32 is 1 (length=1), so that there occurs disagreement between the code length (length=1) read out and the code length data L, which has been initialized to 0, and therefore, the process proceeds to a step S24, wherein the input data-acquiring circuit 35 acquires (lengthxe2x88x92L) bits (equal to 1 bit in the present case, since L has been initialized to 0) from a stream of input data. That is, the input data D is shifted leftward by the (lengthxe2x88x92L) bits, and the input data which is (lengthxe2x88x92L) bits long and has been acquired is added to the shifted input data to update the input data D. In the case of n=0, the original input data D has been initialized to 0, so that the updated input data D is set to data which is 1 bit long from the start position thereof. Then, the value of the code length data L is set to the code length (length=1).
After executing the step S24, or when the code length read out in the step S22 agrees with the code length data L (YES to step S23), the process proceeds to a step S25, wherein a codeword having the address #n is read out from the codeword table 31. Then, it is determined in a step S26 whether or not the codeword read out agrees with the input data D. If the result shows the agreement between the codeword and the input data D, decoded data stored in the address #n of the data table 33 is read out from the data table 33, followed by terminating the decoding of the Huffman encoded data. Then, to decode the next input data, the process starting with the step S21 as described above is carried out again.
On the other hand, if the codeword read out and the input data D do not agree with each other, the program proceeds to a step S28, wherein the count adr of the counter 34 is incremented by 1, and then the process returns to the step S22, so as to repeat the process described above as to a new address (n+1).
Thus, by using the memory storing the Huffman coding table, input data encoded by Huffman coding can be decoded in a round-robin fashion.
It should be noted that there have been proposed various kinds of the Huffman decoding method and decoder other than the above-described one, including a method of using a memory with addresses having the maximum code length, a method of tracing a code tree for each bit, and a method of decoding in a parallel fashion by using a plurality of memories.
In the case of the Huffman decoding method using the Huffman coding table described above, all information of decoding data, code lengths, and codewords is necessary, which increases the required memory capacity of the Huffman coding table. Further, this method is a sequential search-based method which repeatedly carries out a determining process until the agreement between input data and a codeword occurs, and therefore, if data having a long code length is retrieved, the number of times of looking up the table becomes very large, which causes a low efficiency of the decoding process.
Further, in the case of the method using addresses having the maximum code length, it is possible to carry out decoding at a high speed, but it necessitates a very large memory capacity.
Also, in the case of the method of performing parallel processing in order to increase the processing speed, the size of a circuit of the decoder is increased.
It is a first object of the present invention to provide a Huffman decoding method and decoder which is capable of carrying out a decoding process at a high speed with a small memory capacity, and requires only a small-sized circuit, and a storage medium storing a program for executing the Huffman decoding method.
It is a second object of the present invention to provide a Huffman decoding table for use in the Huffman decoding method and decoder, and a method of preparing the Huffman decoding table, a storage medium storing a program for executing the method of preparing the Huffman decoding table.
To attain the first object, according to a first aspect of the invention, there is provided a Huffman decoding method of decoding input data encoded by a Huffman code, comprising the steps of preparing a table describing a binary tree corresponding to the Huffman code and having leaves each storing data, and carrying out a binary tree-based search of the table, based on the input data sequentially acquired by at least one bit to thereby decode the input data encoded by the Huffman code.
Preferably, the binary tree has first nodes having the leaves connected thereto, second nodes having no leaves connected thereto, and the table stores words corresponding to the leaves of the binary tree, and words corresponding to the second nodes having no leaves connected theretp. The table stores, as the words corresponding to the leaves of the binary tree, decoded data corresponding to the data stored in the leaves, and flags for controlling outputting of the decoded data. The table also stores, as each of the words corresponding to the second nodes having no leaves connected thereto, and address of a word corresponding to one of the first and second nodes connected as branches to each of the second nodes, and a flag for controlling whether or not each of the second nodes should be branched to the address.
To attain the first object, according to a second aspect of the invention, there is provided a Huffman decoder that decodes input data encoded by a Huffman code, comprising a table describing a binary tree corresponding to the Huffman code, a bit-extracting and determining section that extracts one bit by one bit from the input data and determines a value of the extracted one bit, an address generating section that generates a read address for the table, a read address-controlling section that controls the read address for the table to be outputted by the address generating section according to the value of the one bit extracted by the bit-extracting and determining section, and an output section that carries out a binary tree-based search of the table, and outputs decoded data corresponding to the input data.
To attain the first object, according to a third aspect of the invention, there is provided a computer-readable storage medium storing a program for executing a Huffman decoding method of decoding input data encoded by a Huffman code, the program comprising a module for preparing a table describing a binary tree corresponding to the Huffman code and having leaves each storing data, and a module for carrying out a binary tree-based search of the table, based on the input data sequentially acquired by at least one to thereby decode the input data encoded by the Huffman code.
To attain the second object, according to a fourth aspect of the invention, there is provided a Huffman decoding table that describes a binary tree corresponding to a Huffman code and having leaves each storing data, wherein the binary tree has first nodes having the leaves connected thereto, second nodes having no leaves connected thereto, and the table stores words corresponding to the leaves of the binary tree, and words corresponding to the second nodes having no leaves connected thereto. The table stores, as the words corresponding to the leaves of the binary tree, decoded data corresponding to data stored in the leaves, and flags for controlling output of the decoded data. The table stores, as each of the words corresponding to the second nodes having no leaves connected thereto, an address of a word corresponding to one of two of the first and second nodes connected as branches to each of the second nodes, and a flag for controlling whether or not each of the second node should be branched to the address.
To attain the second object, according to a fifth aspect of the invention, there is provided a method of preparing a Huffman decoding table for decoding data encoded by a Huffman code, comprising the steps of a first step of preparing a table describing a binary tree correspondin9 to the Huffman code and having leaves each storing data from a Huffman code table describing the Huffman code, the binary tree having first node having the leaves connected thereto, and second nodes having leaves connected thereto, and a second step of preparing words each comprising decoded data corresponding to the data stored in each of the leaves, and a flag for controlling outputting of the decoded data, in a manner associated with the leaves of the binary tree prepared in the first step. A third step of the method is preparing words each comprising an address of a word corresponding to one of two of the first or second nodes connected as branches to each of the second nodes, and a flag for controlling whether or not each of the second nodes should be brapched to the address, and a fourth step of the method is arranging the words prepared in the second step and the third step, in order of search of the binary tree.
To attain the second object, according to a sixth aspect of the invention, there is provided a computer-readable storage medium storing a program for executing a method of preparing a Huffman decoding table for decoding data encoded by a Huffman code, the program comprising a first module of preparing a table describing a binary tree corresponding to the Huffman code and having leaves each storing data from a Huffman code table describing the Huffman code, the binary tree having first node having the leaves connected thereto, and second nodes having leaves connected thereto, and a second module for preparing words each comprising decoded data corresponding to the data stored in each of the leaves, and a flag for controlling outputting of the decoded data, in a manner associated with the leaves of the binary tree prepared in the first step. The program includes a third module for preparing words each comprising an address of a word corresponding to one of two of the first or second nodes connected as branches to each of the second nodes, and a flag for controlling whether or not each of the second nodes should be brapched to the address, and a fourth module for arranging the words prepared in the second module and the third module in orde of search of the binary tree.
The above and other objects of the present invention will become more apparent from the following detailed description taken in conjunction with the accompanying drawings.